package org.usmile.algorithms.learn.graph.direction;

import org.usmile.algorithms.learn.graph.Graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.TreeSet;

public class DirectionAdjSet implements Graph {
    private final int v;
    private final TreeSet<Integer>[] adj;

    private final int[] inDegrees;

    private final int[] outDegrees;

    private int e;

    @SuppressWarnings("unchecked")
    public DirectionAdjSet(int v) {
        this.v = v;
        this.adj = new TreeSet[v];
        this.inDegrees = new int[v];
        this.outDegrees = new int[v];

        for (int i = 0; i < v; i++) {
            this.adj[i] = new TreeSet<>();
        }
    }

    @Override
    public int getV() {
        return this.v;
    }

    @Override
    public int getE() {
        return this.e;
    }

    @Override
    public void addEdge(int v, int w) {
        if (w == v || w >= this.v || v >= this.v) {
            return;
        }
        if (adj[w].contains(v)) {
            return;
        }

        adj[v].add(w);
        outDegrees[v]++;
        inDegrees[w]++;

        e++;
    }

    @Override
    public boolean hasEdge(int v, int w) {
        if (w >= this.v || v >= this.v) {
            return false;
        }

        return adj[v].contains(w);
    }

    @Override
    public Collection<Integer> adj(int v) {
        if (v >= this.v) {
            return new ArrayList<>();
        }

        return adj[v];
    }

    @Override
    public int degree(int v) {
        return adj(v).size();
    }

    public int inDegrees(int v) {
        return inDegrees[v];
    }

    public int outDegrees(int v) {
        return outDegrees[v];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("顶点数 = %d，边数 = %d \n", v, e));
        for (int v = 0; v < this.v; v++) {
            sb.append(v).append(": ");
            for (int w : adj[v]) {
                sb.append(w).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        DirectionAdjSet adjSet = new DirectionAdjSet(4);
        adjSet.addEdge(0, 1);
        adjSet.addEdge(1, 2);
        adjSet.addEdge(1, 3);
        adjSet.addEdge(3, 2);
        System.out.println(adjSet.adj(1));
        System.out.println(adjSet.inDegrees(1));
        System.out.println(adjSet.outDegrees(1));
        System.out.println(adjSet);
    }
}